package com.dycong.common.dataStructuresAndAlgorithms;


import org.junit.Test;

/**
 * Created by dycong on 2017/5/3.
 */
public class LinCode {
    /*
       给定 n 个非负整数 a1, a2, ..., an,
       每个数代表了坐标中的一个点 (i, ai)。画 n 条垂直线，使得 i 垂直线的两个端点分别为(i, ai)和(i, 0)。找到两条线，使得其与 x 轴共同构成一个容器，以容纳最多水。
        */
    @org.junit.Test
    public void max() {
        Integer[] ints = {7, 8, 9, 1, 2, 3, 4, 5, 6};
        shellsort(ints);
        int maxInteger = ints[ints.length - 1];
        int result = 0;
        for (int i : ints) {
            if (i < maxInteger) {
                int t = (maxInteger - i) * i;
                if (t > result) {
                    result = t;
                }
            }
        }
        System.out.println(result);
    }

    public static void shellsort(Comparable[] a) {
        int j;
/* 1*/
        for (int gap = a.length / 2; gap > 0; gap /= 2)
/* 2*/
            for (int i = gap; i < a.length; i++) {
/* 3*/
                Comparable tmp = a[i];
/* 4*/
                for (j = i; j >= gap &&
                        tmp.compareTo(a[j - gap]) < 0; j -= gap)
/* 5*/
                    a[j] = a[j - gap];
/* 6*/
                a[j] = tmp;
            }
    }
}
